#include<iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <stack>
#include <set>
#include <map>
using namespace std;
class Solution {
public:
    bool pd[3][9][10];
    bool pdt[10];
    vector<vector<char>> board;
    void solveSudoku(vector<vector<char>>& boardt) {
        this->board = boardt;
        memset(pd, 0, sizeof pd);
        for (int i = 0; i < 9; i++)
        {
            for (int j = 0; j < 9; j++)
            {
                int t = board[i][j] - '0';
                if (t == '.' - '0')continue;
                pd[0][i][t] = 1;
                pd[1][j][t] = 1;
                pd[2][i / 3 * 3 + j / 3][t] = 1;
            }
        }
        sol(0, 0);
        boardt= this->board;
    }
    bool sol(int x, int y)
    {
        int i=x, j=y;
        while (i < 9)
        {
            
            if (board[i][j] == '.')break;
            j++;
            i += j / 9;
            j %= 9;
        }
        if (i >= 9 || j >= 9)return 1;
        x = i + (j + 1) / 9;
        y = (j + 1) % 9;
        for (int it=1;it<=9;it++)
        {
            if (pd[0][i][it] || pd[1][j][it] || pd[2][i / 3 * 3 + j / 3][it])continue;
            board[i][j] = it + '0';
            pd[0][i][it] = 1;
            pd[1][j][it] = 1;
            pd[2][i / 3 * 3 + j / 3][it] = 1;
            if (sol(x, y))return 1;
            pd[0][i][it] = 0;
            pd[1][j][it] = 0;
            pd[2][i / 3 * 3 + j / 3][it ] = 0;
            board[i][j] = '.';

        }
        return 0;
    }
};
int main()
{ 
    Solution sol;
}